package basic.courseLearn15.problem;

import org.junit.Test;

public class Robot {

    @Test
    public void test_solution_1(){
        int k = 2;
        int start = 2;
        int end = 1;
        int currentIndex = start;
        int power = 3;
        System.out.println("solution_1 = " + solution_1(k, start, end, currentIndex, power));
    }

    @Test
    public void test_solution_2(){
        int k = 5;
        int start = 1;
        int end = 3;
        int currentIndex = start;
        int power = 4;
        int[][] results = new int[k+1][power+1];
        //初始化results数组
        for(int i=1;i<=k;i++){
            for(int j=1;j<=power;j++){
                results[i][j] = -1;
            }
        }
        System.out.println("solution_2 = " + solution_2(k, start, end, currentIndex, power,results));
    }

    @Test
    public void test_solution_3(){
        int k = 1;
        int start = 1;
        int end = 1;
        int currentIndex = start;
        int power = 4;
        System.out.println("solution_3 = " + solution_3(k, start, end, currentIndex, power));
    }



    @Test
    public void test_checkResult(){
        int count = 10000;
        int range = 10;
        checkResult(count,range);
    }

    /**
     * 对数器
     * @param count 次数
     * @param range 范围（1-range）
     */
    public void checkResult(int count,int range){
        System.out.println("对数器开始运行");
        for (int i = 0; i < count; i++) {
            System.out.println(""+(i+1)+"次测试开始");
            int power = (int) (Math.random() * (range+ 1 )) ;//[0，range]
            int k = (int) (Math.random() * (range-1)) + 2; //[2，range]
            int start = (int) (Math.random() * k) + 1; //[1，k]
            int end = (int) (Math.random() * k) + 1; //[1，k]
            int currentIndex = start;
            int[][] results = new int[k+1][power+1];
            //初始化results数组
            for(int m=1;m<=k;m++){
                for(int n=1;n<=power;n++){
                    results[m][n] = -1;
                }
            }
            int result_1 = solution_1(k, start, end, currentIndex, power);
            int result_2 = solution_2(k, start, end, currentIndex, power,results);
            int result_3 = solution_3(k, start, end, currentIndex, power);
            if(result_1!= result_2 || result_1!= result_3){
                System.out.println("第"+(i+1)+"次测试失败");
                System.out.println("k="+k+",start="+start+",end="+end+",currentIndex="+currentIndex+",power="+power);
                System.out.println("result_1="+result_1+",result_2="+result_2+",result_3="+result_3);
                return;
            }

        }
        System.out.println("\n对数器运行结束，全部测试通过");

    }


    /**
     * 解法1：暴力递归
     * @param k 位置个数，1--k
     * @param start 起始位置
     * @param end 结束位置
     * @param currentIndex 当前位置
     * @param power 剩余部署
     * @return 方案个数
     */
    public int solution_1(int k,int start,int end,int currentIndex,int power){

        //1. 到达终点
        if(currentIndex == end && power == 0){
            return 1;
        }
        //2. 到不了终点
        if(currentIndex != end && power == 0){
            return 0;
        }
        //3. 根据情况判断

        if (currentIndex == 1){         //左边缘
            return solution_1(k,start,end,2,power-1);
        } else if (currentIndex == k){  //右边缘
            return solution_1(k,start,end,k-1,power-1);
        }else{
            return solution_1(k,start,end,currentIndex-1,power-1) +
                    solution_1(k,start,end,currentIndex+1,power-1);
        }
    }



    /**
     * 解法2：记忆搜索：根据暴力搜索改进，利用缓存
     * @param k 位置个数，1--k
     * @param start 起始位置
     * @param end 结束位置
     * @param currentIndex 当前位置
     * @param power 剩余部署
     * @return 方案个数
     */
    public int solution_2(int k,int start,int end,int currentIndex,int power,int[][] results){

        //1. 到达终点
        if(currentIndex == end && power == 0){
            return 1;
        }
        //2. 到不了终点
        if(currentIndex != end && power == 0){
            return 0;
        }
        //3. 判断是否已经计算过
        if(results[currentIndex][power] != -1){
            return results[currentIndex][power];
        }

        //3. 根据情况判断
        if (currentIndex == 1){         //左边缘
            int value = solution_1(k,start,end,2,power-1);
            results[currentIndex][power] = value;
            return value;
        } else if (currentIndex == k){  //右边缘
            int value = solution_1(k,start,end,k-1,power-1);
            results[currentIndex][power] = value;
            return value;
        }else{
            int value =solution_1(k,start,end,currentIndex-1,power-1) +
                    solution_1(k,start,end,currentIndex+1,power-1) ;
            results[currentIndex][power] = value;
            return value;
        }
    }

    /**
     * 解法3：严格表搜索：根据暴力搜索改进，利用位置
     * @param k 位置个数，1--k
     * @param start 起始位置
     * @param end 结束位置
     * @param currentIndex 当前位置
     * @param power 剩余部署
     * @return 方案个数
     */
    public int solution_3(int k,int start,int end,int currentIndex,int power){

        //1. 初始化结果数组
        int[][] results = new int[k+1][power+1];
        //2. 初始化结果数组
        for(int i=1;i<=k;i++){
            for(int j=0;j<=power;j++){
                results[i][j] = -1;
            }
        }
        for (int i = 1; i <= k; i++) {
            if (i == end){
                results[i][0] = 1;
            }else {
                results[i][0] = 0;
            }
        }
        //3. 根据暴力递归得出推导式，进行计算
        for (int j = 1; j <= power; j++){
            for (int i = 1; i <= k; i++) {
                if (i == 1){
                    results[i][j] = results[2][j-1];
                } else if (i == k){
                    results[i][j] = results[k-1][j-1];
                }else{
                    results[i][j] = results[i-1][j-1] + results[i+1][j-1];
                }
            }
        }


        return results[currentIndex][power];
    }





}
